
//? 时间复杂度最好O(nlog2n) 最坏O(n2)（数组有序） 不稳定 空间O(log2n)
function quickSort(nums) {
    //? 递归出口
    if (nums.length <= 1) return nums
    //? 基准值选择第一个元素 这里是以索引的方式
    let mid = 0
    let left = []
    let right = []
    //? 小的放左数组 大的放右数组
    for (let i = 1; i < nums.length; i ++) {
        if (nums[i] < nums[mid]) {
            left.push(nums[i])
        }
        else {
            right.push(nums[i])
        }
    }
    //? 这里递归   返回的是左边数组的排序结果 + key基准值 + 右边数组的排序结果
    return [...quickSort(left), nums[mid], ...quickSort(right)]
}
console.log(quickSort([4, 2, 8, 9, 1, 7, 10, 3, 0, 2]));
